package com.michael.demos.base.java.arithmetic;

import java.util.HashMap;

/**
 * 类功能描述:
 * <pre>
 *   算法 - LRU算法(Redis底层有实现)
 *   LRU = Least Recently Used  最近最少使用
 *   相关数据结构：哈希链表
 *
 *   LRU实现相关原理：
 *   1. 哈希链表结构：有序双向链表中存储KEY-VALUE
 *   2. 排序方式：把KEY-VALUE按最后使用时间进行排序
 *   3. 数据插入：按照KEY被访问的时间顺序依次从链表右端插入
 *   4. 数据更新：对于已存在的KEY，将对应KEY-VALUE移至最右
 *   5. 数据删除：当插入达到容量上限，依次删除最左的数据
 *
 *   PS:当前只为模拟LRU，非线程安全
 *   参考：小灰的算法之旅
 *
 *   @see java.util.LinkedHashMap
 * </pre>
 *
 * @author Michael
 * @version 1.0
 * @date 2021/01/22 08:33
 */
public final class LRUCache {

    private Node head;
    private Node tail;

    /**
     * 存储数量上限
     */
    private int limit;

    private HashMap<String, Node> hashMap;

    public LRUCache(int limit) {
        this.limit = limit;
        hashMap = new HashMap<>();
    }

    public String get(String key) {
        Node node = hashMap.get(key);
        if (node == null) {
            return null;
        }
        refreshNode(node);
        print();
        return node.value;
    }

    public void put(String key, String value) {
        Node node = hashMap.get(key);
        if (node == null) {
            // KEY不存在，插入数据
            if (hashMap.size() >= limit) {
                // 空间不足，删除头部数据
                String oldKey = removeNode(head);
                hashMap.remove(oldKey);
            }
            node = new Node(key, value);
            addNode(node);
            hashMap.put(key, node);
        } else {
            // KEY 存在，刷新调整
            node.value = value;
            refreshNode(node);
        }
        print();
    }

    /**
     * 刷新被访问节点的位置
     */
    public void refreshNode(Node node) {
        // 访问尾节点，不需要移动数据
        if (node == tail) {
            return;
        }
        // 移除节点
        removeNode(node);
        // 重新插入节点
        addNode(node);
    }

    /**
     * 删除节点
     */
    private String removeNode(Node node) {
        if (node == head && node == tail) {
            // 存储清空
            head = tail = null;
        } else if (node == head) {
            // 移除头节点
            head = head.next;
            head.pre = null;
        } else if (node == tail) {
            // 移除尾节点
            tail = tail.pre;
            tail.next = null;
        } else {
            // 移除中间节点
            node.pre.next = node.next;
            node.next.pre = node.pre;
        }
        return node.key;
    }

    /**
     * 在尾部插入节点
     */
    private void addNode(Node node) {
        if (tail != null) {
            tail.next = node;
            node.pre = tail;
            node.next = null;
        }
        tail = node;
        if (head == null) {
            head = node;
        }
    }

    /**
     * 打印缓存
     */
    public void print() {

        if (head != null) {
            System.out.print("当前存储的数据为 -> ");
            Node index = head;
            while (index != null) {
                System.out.print(index.key + "\t");
//                System.out.print(index.key + "\t" + index.value + "\t");
                index = index.next;
            }
            System.out.println();

        }
    }

    private static class Node {
        public Node pre;
        public Node next;
        public String key;
        public String value;

        public Node(String key, String value) {
            this.key = key;
            this.value = value;
        }
    }

    public static void main(String[] args) {
        LRUCache cache = new LRUCache(5);
        cache.put("1", "我是用户1");
        cache.put("2", "我是用户2");
        cache.put("3", "我是用户3");
        cache.put("4", "我是用户4");
        cache.put("5", "我是用户5");
        cache.get("2");
        cache.put("3", "我是用户3的更新");
        cache.put("6", "我是用户6");
        cache.get("3");
        cache.get("5");
        cache.put("1", "我是用户1");

        System.out.println("获取缓存数据 KEY(6) -> " + cache.get("6"));
        System.out.println("获取缓存数据 KEY(1) -> " + cache.get("1"));
    }
}
